home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 1 / Cream of the Crop 1.iso / PROGRAM / NTUMIN10.ARJ / CAMPA.C < prev    next >
C/C++ Source or Header  |  1992-03-09  |  19KB  |  557 lines
  1. /****************************************************************************
  2.  *
  3.  *      Program name : CAMPA.C
  4.  *
  5.  *      This is the actual minimization algorithm with slight modification
  6.  *    from the original CAMP algorithm. In phase II, in selecting the
  7.  *    adjacent, mi to shrink off, the 1st one with largest wi and is
  8.  *    already covered is chosen.
  9.  *
  10.  * --------------------------------------------------------------------------
  11.  *    Copyright (c) 1992. All Rights Reserved. Nanyang Technological
  12.  *    University.
  13.  *
  14.  *    You are free to use, copy and distribute this software and its
  15.  *    documentation providing that:
  16.  *
  17.  *        NO FEE IS CHARGED FOR USE, COPYING OR DISTRIBUTION.
  18.  *
  19.  *        IT IS NOT MODIFIED IN ANY WAY.
  20.  *
  21.  *        THE COPYRIGHT NOTICE APPEAR IN ALL COPIES.
  22.  *
  23.  *    This program is provided "AS IS" without any warranty, expressed or
  24.  *    implied, including but not limited to fitness for any particular
  25.  *    purpose.
  26.  *
  27.  *    If you find NTUMIN fast, easy, and useful, a note or comment would be
  28.  *    appreciated. Please send to:
  29.  *
  30.  *        Boon-Tiong Tan or Othman Bin Ahmad
  31.  *        School of EEE
  32.  *        Nanyang Technological University
  33.  *        Nanyang Avenue
  34.  *        Singapore 2263
  35.  *        Republic of Singapore
  36.  *
  37.  ***************************************************************************/
  38.  
  39. #include <stdio.h>
  40. #include <stdlib.h>
  41. #include <string.h>
  42. #define mask8 255
  43.  
  44. unsigned char   *campa(a, b)              /* pointer to a & b array passed */
  45. unsigned char   *a, *b;
  46.  
  47. {
  48.    unsigned short   pterm, ma, mb, *pm, pos;
  49.    unsigned short   *ca, *mp, m_cnt, a_cnt;
  50.    unsigned  long   m, j, size, addr, count, count1, topow();
  51.    register  long   i, wo, wi;
  52.          char   test;
  53.    unsigned  char   *c, *d, *e, *s, *temp, *cp, *mt, *at, *ad;
  54.    unsigned  char   n, adj, adj0, adji, adjacency(), nspm, cover;
  55.    unsigned  char   *adjacent(), *reduce(), *cpt(), *ssm(), adj_of_mi();
  56.  
  57.  
  58.    mb = *(b+2)<<8 | *(b+1);            /* no. of minterms in b-array */
  59.  
  60.    n    = *a;                          /* no. of variables */
  61.    nspm = *(a+3);                      /* no. of bytes/minterm */
  62.    ma = *(a+2)<<8 | *(a+1);           /* no. of minterms in a-array */
  63.  
  64.    temp = (unsigned char *) malloc(nspm+1);        /* temporary storage */
  65.    if (temp == 0)
  66.       {
  67.      printf("Out of memory -- CAMPA, *temp\n");
  68.      printf("Program terminated - 1\n");
  69.      exit(0);
  70.       }
  71.  
  72.    s = (unsigned char *) malloc(4);                /* header of s-array */
  73.    if (s == 0)
  74.       {
  75.      printf("Out of memory -- CAMPA, *s\n");
  76.      printf("Program terminated - 2\n");
  77.      exit(0);
  78.       }
  79.  
  80.  
  81.    /***********\
  82.     * PHASE I *
  83.    \***********/
  84.  
  85.    pterm = 0;                                /* no. of product term */
  86.    count = 0;                                /* no. of terms stored for phase II */
  87.  
  88.    /***
  89.     ***  DETERMINE ADJACENCY OF ALL MINTERMS AND GENERATE THEIR CPT
  90.     ***/
  91.  
  92.    for (i=0; i<mb; i++)                      /* for all minterms in b-array */
  93.       {
  94.      *b = n;                             /* assign back to n */
  95.  
  96.      memcpy(temp, (b+4+nspm*i), nspm);   /* pick a minterm from b-array */
  97.      c = adjacent(temp, a, 255);         /* obtain the adjacent terms */
  98.      adj = *(c+1);                       /* adjacency of minterm */
  99.      d = cpt(c);                         /* generate CPT */
  100.  
  101.      /***
  102.       ***  MINIMIZE ALL MINTERMS WITH ADJACENCY OF 0 & 1 FIRST
  103.       ***/
  104.  
  105.      if (adj <= 1)                       /* adjacency 0 or 1 */
  106.         {
  107.            s = (unsigned char *) realloc(s,4+n*(pterm+1));   /* more space */
  108.            if (s == 0)
  109.           {
  110.              printf("Out of memory -- CAMPA, *s\n");
  111.              printf("Program terminated - 3\n");
  112.              exit(0);
  113.           }
  114.            memcpy ((s+4+n*pterm),d,n);   /* add CPT to soln array */
  115.            pterm++;                      /* product term count */
  116.  
  117.            b = reduce(c,b,i);            /* remove minterms covered from b-array */
  118.            i = (char) *b;                /* index pointer of b-array */
  119.            mb = *(b+2)<<8 | *(b+1);      /* value of mb altered in b-array */
  120.         }
  121.      else                                /* adj > 1 */
  122.         {
  123.  
  124.            /***
  125.         ***  MINTERMS WITH ADJACENCY GREATER THAN 1, GENERATE SSM AND TEST FOR COVERAGE
  126.         ***/
  127.  
  128.            e = ssm(d);                          /* generate SSM */
  129.            m = topow(*(e+1));                   /* no. of SSM terms */
  130.  
  131.            for (j=0; j<m; j++)                  /* check for SSM coverage */
  132.           {
  133.              memcpy (temp, (e+4+nspm*j), nspm);   /* pick SSM term */
  134.              test = exist (temp, a, ma);
  135.              if (test == -1)                /* minterm not in a-array */
  136.             break;
  137.           }
  138.  
  139.            /***
  140.         ***  ALL SSM COVERED BY THE FUNCTION, SELECT CPT AS PRODUCT TERM
  141.         ***/
  142.  
  143.            if (test == 0)                        /* all SSM's covered by fn */
  144.           {
  145.              if (m > 65536)                  /* too many SSM terms */
  146.             {
  147.                printf("Product Term Too Huge \n");
  148.                printf("Program terminated \n");
  149.                exit(0);
  150.             }
  151.              *(e+1) = (m-1) & mask8;         /* no. of SSM terms minus 1 */
  152.              *(e+2) = (m-1)>>8 & mask8;
  153.              b = reduce(e,b,i);              /* remove minterms covered from b-array */
  154.              i = (char) *b;                  /* index pointer of b-array */
  155.              mb = *(b+2)<<8 | *(b+1);        /* no. of minterms in b-array */
  156.  
  157.              s = (unsigned char *) realloc(s, 4+n*(pterm+1)); /* more space */
  158.              if (s == 0)
  159.             {
  160.                printf("Out of memory -- CAMPA, *s\n");
  161.                printf("Program terminated - 4\n");
  162.                exit(0);
  163.             }
  164.              memcpy((s+4+n*pterm),d,n);     /* add CPT to soln array */
  165.              pterm++;                       /* no. of product terms */
  166.              free(e);                   /* free pointer */
  167.           }
  168.            else
  169.           {
  170.              free(e);                 /* free pointer */
  171.  
  172.              /***
  173.               ***  NOT COVERED, STORE UNCOVERED MINTERMS, ITS CORRESPONDING
  174.               ***  ADJACENCY, ADJACENT TERMS AND CPT FOR PHASE II
  175.               ***/
  176.  
  177.              count++;                       /* no. of terms for phase II */
  178.              if (count==1)                  /* 1st uncovered term */
  179.             {
  180.                ad = (unsigned char *) malloc(2);    /* array of adjacency */
  181.                if (ad==0)
  182.                   {
  183.                  printf("Out of memory -- CAMPA, *ad\n");
  184.                  printf("Program terminated - 5\n");
  185.                  exit(0);
  186.                   }
  187.                cp = (unsigned char *) malloc(n);     /* array of CPT's */
  188.                if (cp==0)
  189.                   {
  190.                  printf("Out of memory -- CAMPA, *cp\n");
  191.                  printf("Program terminated - 6\n");
  192.                  exit(0);
  193.                   }
  194.                mt = (unsigned char *) malloc(4+nspm*count);  /* array of minterms */
  195.                if (mt==0)
  196.                   {
  197.                  printf("Out of memory -- CAMPA, *mt\n");
  198.                  printf("Program terminated - 7\n");
  199.                  exit(0);
  200.                   }
  201.                size = 4 + nspm*(1+adj);                         /* addr counter of at-array */
  202.                at = (unsigned char *) malloc (4+nspm*(1+adj));  /* all adj terms from c-arrays */
  203.                if (at==0)
  204.                   {
  205.                  printf("Out of memory -- CAMPA, *at\n");
  206.                  printf("Program terminated - 8\n");
  207.                  exit(0);
  208.                   }
  209.                ca = (unsigned short *) malloc(2);          /* array of addr of at-array */
  210.                if (ca==0)
  211.                   {
  212.                  printf("Out of memory -- CAMPA, *ca\n");
  213.                  printf("Program terminated - 9\n");
  214.                  exit(0);
  215.                   }
  216.                addr = 0;         /* starting address of at-array */
  217.             }
  218.              else                    /* subsequent uncovered terms */
  219.             {
  220.                ad = (unsigned char *) realloc(ad, count);    /* adjacency */
  221.                if (ad==0)
  222.                   {
  223.                  printf("Out of memory -- CAMPA, *ad\n");
  224.                  printf("Program terminated - 10\n");
  225.                  exit(0);
  226.                   }
  227.                cp = (unsigned char *) realloc(cp,n*count);    /* CPT's */
  228.                if (cp==0)
  229.                   {
  230.                  printf("Out of memory -- CAMPA, *cp\n");
  231.                  printf("Program terminated - 11\n");
  232.                  exit(0);
  233.                   }
  234.                mt = (unsigned char *) realloc(mt,4+nspm*count); /* minterms */
  235.                if (mt==0)
  236.                   {
  237.                  printf("Out of memory -- CAMPA, *mt\n");
  238.                  printf("Program terminated - 12\n");
  239.                  exit(0);
  240.                   }
  241.                size+=4+nspm*(1+adj);                     /* addr counter of at-array */
  242.                at = (unsigned char *) realloc (at,size); /* all adj terms from c-arrays */
  243.                if (at==0)
  244.                   {
  245.                  printf("Out of memory -- CAMPA, *at\n");
  246.                  printf("Program terminated - 13\n");
  247.                  exit(0);
  248.                   }
  249.                ca = (unsigned short *) realloc(ca,2*count);       /* addr of at-array */
  250.                if (ca==0)
  251.                   {
  252.                  printf("Out of memory -- CAMPA, *ca\n");
  253.                  printf("Program terminated - 14\n");
  254.                  exit(0);
  255.                   }
  256.             }
  257.  
  258.              /***
  259.               ***  STORE IN ARRAYS FOR PHASE II
  260.               ***/
  261.  
  262.              *(ad+(count-1)) = adj;                           /* adjacency */
  263.              memcpy((cp+n*(count-1)),d,n);                    /* CPT's */
  264.              memcpy((mt+4+nspm*(count-1)),(b+4+nspm*i),nspm); /* minterms */
  265.              memcpy((at+addr),c,4+nspm*(1+adj));              /* adj terms */
  266.              *(ca+(count-1)) = addr;                   /* addr of at-array */
  267.              addr = size;                              /* update addr */
  268.           }
  269.         }
  270.      free(c);                     /* free pointers */
  271.      free(d);
  272.       }
  273.    count1 = count;                   /* no. of terms for phase II */
  274.  
  275.  
  276.    /************\
  277.     * PHASE II *
  278.    \************/
  279.  
  280.    while (count > 0)               /* some terms stored for phase II */
  281.       {
  282.      /***
  283.       ***  SELECT NEXT MINTERM WITH THE LOWEST ADJACENCY AND AT LEAST ONE OF
  284.       ***  ITS ADJACENT TERMS PREVIOUSLY COVERED
  285.       ***/
  286.  
  287.      adj0 = 255;               /* set to max of 8-bit */
  288.  
  289.      for (i=0; i<count1; i++)               /* do for all adj terms in phase II */
  290.         {
  291.            if (*(ad+i)<adj0 && *(ad+i)!=0)  /* choose minterms with lowest adj */
  292.           {
  293.              if (adj0 != 255)           /* not the first lowest */
  294.             free(mp);
  295.              adj0 = *(ad+i);            /* new lowest value */
  296.              m_cnt = 1;                 /* reset count to 1 */
  297.  
  298.              mp = (unsigned short *) malloc(2);     /* space for pos of lowest adj */
  299.              if (mp==0)
  300.             {
  301.                printf("Out of memory -- CAMPA, *mp\n");
  302.                printf("Program terminated - 15\n");
  303.                exit(0);
  304.             }
  305.              *mp = i;                               /* first element */
  306.           }
  307.            else if (*(ad+i) == adj0)                    /* adj as large */
  308.           {
  309.              m_cnt++;                               /* no. of element in mp-array */
  310.              mp = (unsigned short *) realloc(mp, 2*m_cnt); /* more space */
  311.              if (mp==0)
  312.             {
  313.                printf("Out of memory -- CAMPA, *mp\n");
  314.                printf("Program terminated - 16\n");
  315.                exit(0);
  316.             }
  317.              *(mp+m_cnt-1) = i;            /* elements in mp-array */
  318.           }
  319.         }
  320.  
  321.      /***
  322.       ***  SELECT FROM MP-ARRAY, A MINTERM WITH AT LEAST ONE ADJACENT TERM PREVIOSLY
  323.       ***  COVERED
  324.       ***/
  325.  
  326.      for (i=0; i<m_cnt; i++)                 /* do for all in mp-array */
  327.         {
  328.            adj = *(ad+ *(mp+i));             /* adjacency from ad-array */
  329.  
  330.            c = (unsigned char *) malloc(4+nspm*(1+adj));  /* space for adj terms */
  331.            if (c == 0)
  332.           {
  333.              printf("Out of memory -- CAMPA, *c\n");
  334.              printf("Program terminated - 17\n");
  335.              exit(0);
  336.           }
  337.            memcpy(c, (at+ *(ca+ *(mp+i))), 4+nspm*(1+adj));  /* adj terms from at-array */
  338.  
  339.            for (j=0; j<adj; j++)          /* check for at least 1 adj term covered */
  340.           {
  341.              memcpy(temp, (c+4+nspm*(1+j)),nspm);
  342.              test = exist(temp,b,mb);
  343.              if (test == -1)          /* adj term covered */
  344.             break;
  345.           }
  346.  
  347.            if (test == -1)                /* adj term covered */
  348.           break;
  349.            else
  350.           free(c);                    /* free pointer */
  351.         }
  352.  
  353.      if (test == -1)                      /* adj term covered */
  354.         pos = *(mp+i);                    /* position of minterm required */
  355.      else                                 /* none of adj terms covered */
  356.         {
  357.            adj = *(ad+ *mp);              /* choose adj of 1st minterm */
  358.            pos = *mp;                     /* position of 1st minterm */
  359.  
  360.            c = (unsigned char *) malloc(4+nspm*(1+adj));   /* space for adj terms */
  361.            if (c == 0)
  362.           {
  363.              printf("Out of memory -- CAMPA, *c\n");
  364.              printf("Program terminated - 18\n");
  365.              exit(0);
  366.           }
  367.            memcpy(c, (at+ *(ca+pos)), 4+nspm*(1+adj));     /* adj terms from at-array */
  368.         }
  369.  
  370.      d = (unsigned char *) malloc(n+1);       /* space for corresponding CPT */
  371.      if (d == 0)
  372.         {
  373.            printf("Out of memory -- CAMPA, *d\n");
  374.            printf("Program terminated - 19\n");
  375.            exit(0);
  376.         }
  377.      memcpy(d, (cp+n*pos), n);       /* corresponding CPT from cp-array */
  378.      *(d+n) = '\0';                  /* terminate with NULL string */
  379.  
  380.      e = ssm(d);                     /* generate SSM */
  381.  
  382.      free(d);                        /* free pointers */
  383.      free(mp);
  384.  
  385.      /***
  386.       ***  KEEP SHRINKING THE CPT UNTIL THE SELECTED MINTERM IS COVERED BY THE FUNCTION
  387.       ***/
  388.  
  389.      cover = 0;                      /* coverage status */
  390.      while (!cover)                  /* do until shrinked CPT is covered */
  391.         {
  392.            /***
  393.         ***  OBTAIN AN ARRAY, PM OF POSITIONS OF ADJACENT TERMS, MI WITH THE LARGEST WI
  394.         ***/
  395.  
  396.            wo = -1;                  /* initial value */
  397.            for (i=0; i<adj; i++)     /* do for all adjacent terms */
  398.           {
  399.              memcpy(temp, (c+4+nspm*(i+1)), nspm);  /* pick adjacent term */
  400.  
  401.              wi = adj_of_mi(temp,e,a);              /* obtain wi */
  402.              if (wi>wo)
  403.             {
  404.                if (wo != -1)                    /* not 1st largest wi */
  405.                   free(pm);
  406.                wo = wi;                         /* new largest */
  407.                a_cnt = 1;                       /* set count to 1 */
  408.  
  409.                pm = (unsigned short *) malloc(2);    /* space for pm-array */
  410.                if (pm == 0)
  411.                   {
  412.                  printf("Out of memory -- CAMPA, *pm\n");
  413.                  printf("Program terminated - 20\n");
  414.                  exit(0);
  415.                   }
  416.                *pm = i;              /* 1st element of pm-array */
  417.             }
  418.              else if (wi==wo)            /* wi as large */
  419.             {
  420.                a_cnt++;              /* no. of elements in pm-array */
  421.  
  422.                pm = (unsigned short *) realloc (pm, 2*a_cnt);  /* more space */
  423.                if (pm == 0)
  424.                   {
  425.                  printf("Out of memory -- CAMPA, *pm\n");
  426.                  printf("Program terminated - 21\n");
  427.                  exit(0);
  428.                   }
  429.                *(pm+a_cnt-1) = i;     /* elements of pm-array */
  430.             }
  431.           }
  432.            free(e);                        /* free pointer */
  433.  
  434.            /***
  435.         ***  SELECT FROM PM-ARRAY, AN ADJACENT TERM THAT HAS ALREADY BEEN COVERED
  436.         ***/
  437.  
  438.            for (i=0; i<a_cnt; i++)         /* do for all minterms in pm-array */
  439.           {
  440.              memcpy(temp, (c+4+nspm*(1+ *(pm+i))), nspm); /* pick adj term */
  441.              test = exist(temp,b,mb);
  442.              if (test == -1)                  /* already covered */
  443.             break;
  444.           }
  445.  
  446.            if (i==a_cnt)                          /* select 1st if all not covered */
  447.           i = 0;
  448.  
  449.            adj--;                                 /* no. of adj terms in c-array */
  450.            *(c+1) = adj;                          /* adjacency after shrinking */
  451.            pos = *(pm+i);                         /* position of adj term to be shrinked */
  452.  
  453.            free(pm);                              /* free pointer */
  454.  
  455.         /***
  456.          ***  SHRINK CPT (REMOVE 1 ADJACENT TERM FROM C-ARRAY), GENERATE NEW CPT,
  457.          ***  SSM AND TEST FOR COVERAGE BY FUNCTION
  458.          ***/
  459.  
  460.            memcpy((c+4+nspm*(1+pos)), (c+4+nspm*(2+pos)), nspm*(adj-pos));  /* shrink c-array */
  461.  
  462.            c = (unsigned char*) realloc(c, 4+nspm*(1+adj));   /* decrease space */
  463.            if (c == 0)
  464.           {
  465.              printf("Out of memory -- CAMPA, *c\n");
  466.              printf("Program terminated - 22\n");
  467.              exit(0);
  468.           }
  469.  
  470.            d = cpt(c);                  /* generate CPT */
  471.            e = ssm(d);                  /* generate SSM */
  472.            m = topow(*(e+1));           /* no. of SSM terms */
  473.  
  474.            for (i=0; i<m; i++)          /* check SSM coverage by function */
  475.           {
  476.              memcpy(temp, (e+4+nspm*i), nspm);   /* pick SSM term */
  477.              test = exist(temp,a,ma);
  478.              if (test == -1)                     /* SSM not covered */
  479.             break;
  480.           }
  481.  
  482.            /***
  483.         ***  SHRINKED SSM COVERED BY FUNCTION, REDUCE B-ARRAY AND
  484.         ***  SELECT SHRINKED CPT AS PRODUCT TERM
  485.         ***/
  486.  
  487.            if (test==0)                      /* SSM covered */
  488.           {
  489.              if (m > 65536)                  /* too many SSM terms */
  490.             {
  491.                printf("Product Term Too Huge \n");
  492.                printf("Program terminated \n");
  493.                exit(0);
  494.             }
  495.              *(e+1) = (m-1) & mask8;         /* no. of SSM terms minus 1 */
  496.              *(e+2) = (m-1)>>8 & mask8;
  497.              b = reduce(e, b, m);        /* remove minterms covered from b-array */
  498.              mb = *(b+2)<<8 | *(b+1);    /* no. of minterms in b-array */
  499.  
  500.              count = mb;                 /* count of no. of minterms not covered */
  501.  
  502.              s = (unsigned char *) realloc(s, 4+n*(pterm+1));   /* more space */
  503.              if (s == 0)
  504.             {
  505.                printf("Out of memory -- CAMP, *s\n");
  506.                printf("Program terminated - 23\n");
  507.                exit(0);
  508.             }
  509.              memcpy ((s+4+n*pterm), d, n);     /* add shrinked CPT to soln array */
  510.              pterm++;                          /* no. of product terms */
  511.  
  512.              cover = 1;                        /* coverage status */
  513.  
  514.              /***
  515.               ***  FLAG TERMS COVERED IN THE AD-ARRAY
  516.               ***/
  517.  
  518.              for (i=0; i<m; i++)               /* flag terms just covered */
  519.             {
  520.                for (j=0; j<count1; j++)    /* do for all terms in mt-array */
  521.                   {
  522.                  test = memcmp((e+4+nspm*i), (mt+4+nspm*j), nspm);
  523.                  if (test==0)
  524.                     {
  525.                        *(ad+j) = 0;    /* flag the adjacency to indicate coverage */
  526.                        break;
  527.                     }
  528.                   }
  529.             }
  530.              free(e);            /* free pointer */
  531.           }
  532.            free (d);                 /* free pointer */
  533.         }
  534.      free(c);                        /* free pointer */
  535.       }
  536.  
  537.    if (count1>0)                  /* some terms stored for phase II */
  538.       {
  539.      free(ad);                /* free pointers */
  540.      free(cp);
  541.      free(mt);
  542.      free(at);
  543.      free(ca);
  544.       }
  545.  
  546.    *s = n;                        /* no. of variables */
  547.    *(s+1) = pterm & mask8;        /* no. of product terms in 2 bytes */
  548.    *(s+2) = pterm>>8 & mask8;
  549.  
  550.    free(temp);                    /* free pointer */
  551.    free(a);
  552.    free(b);
  553.  
  554.    return(s);                     /* return solution array */
  555. }
  556.  
  557.